Nested Sets

The Nested Sets solution stores information with each node that pertains to the set of its descendants rather than the node’s immediate parent. This information can be represented by encoding each node in the tree with two numbers, which we can call nsleft and nsright.

Creating Comments table with nsleft and nsright#

Let’s create the Comments table, with nsright and nsleft as its columns.

Assigning nsleft and nsright#

Each node is given nsleft and nsright numbers in the following way: the value of the nsleft number is always less than the value of the numbers of all of the node’s children, whereas the value of the nsright number is greater than that of all of the node’s children. These numbers have no relation to the comment_id values.

An easy way to assign these values is by following a depth-first traversal of the tree, assigning nsleft numbers incrementally as we descend a branch of the tree and assigning nsright numbers as we ascend back up the branch.

It may be easier to visualize the pattern from the figure below.

Querying the Comments table#

We will see the queries for finding out ancestors and descendants. We will also test queries for counting the depth and finding out the immediate parent.

Finding out descendants of a comment#

Once we have assigned each node with nsleft and nsright, we can use them to find ancestors and descendants of any given node. For example, we can retrieve comment # 4 and its descendants by searching for nodes whose numbers are between the current node’s nsleft and nsright.

Let’s run the query in the following code widget to retrieve comment # 4 and its descendants. We can also update the query to retrieve the descendants of another comment.

Finding out the ancestors of a comment#

We can retrieve comment # 6 and its ancestors by searching for nodes whose numbers span the current node’s numbers.

Let’s run the following query to retrieve the ancestors of comment # 6. We can also edit the query to retrieve the ancestors of another comment.

Counting the depth of a node#

One chief strength of the Nested Sets design is that when we delete a non-leaf node, its descendants are automatically considered direct children of the deleted node’s parents. Although the right and left numbers of each node shown in the illustration have values forming a continuous series, and the difference with adjacent siblings and parents is always one, this is not necessary for the Nested Sets design to preserve the hierarchy. Thus, when gaps in the values result from deleting a node, there is no interruption to the tree structure.

For example, we can count the depth of a given node and delete its parent. Then, when we count the depth of the node again, it would seem to have decreased in depth by one level.

Let’s check the depth of comment 7 in the following playground.

Now, let’s delete the parent of comment 7 and check its depth again. We will find that it has reduced by 1 after the deletion of its parent.

We can check the depth of any comment in the same playground.

Looking for an immediate parent#

However, some queries that are simple in the Adjacency List design, such as retrieving the immediate child or immediate parent, are more complex in the Nested Sets design. The direct parent of a given node c1 is an ancestor of that node, but no other node can exist between them. So, we can use an additional outer join to search for a node that is both an ancestor of c1 and a descendant of the parent. Only if no such node is found (that is, the result of the outer join is null) is the ancestor truly the direct parent of c1.

For example, to find the immediate parent of comment 6, run the query in the following playground and see the output:

How manipulation in a tree affects the model#

Manipulations of the tree — inserting and moving nodes — are generally more complex in the Nested Sets design than they are in other models. When we insert a new node, we need to recalculate all the values to the left and right of the node that are greater than the value to the left of the new node.

This includes the new node’s right siblings, its ancestors, and the right siblings of its ancestors. It also includes descendants if the new node is inserted as a non-leaf node. Assuming the new node is a leaf node, the following statement should update everything necessary:

Let’s retrieve the data in the Comments table in the following playground to see how the query has affected the database.

Nested Sets oddity#

The Nested Sets model is best when it’s more important to perform queries for subtrees quickly and easily than performing operations on individual nodes. Inserting and moving nodes is complex because of the requirement to renumber the left and right values. If our usage of the tree involves frequent insertions, then a Nested Sets approach isn’t the best choice.